use regex::NoExpand;
use std::cell::RefCell;
use std::rc::Rc;
#[derive(Debug)]
struct Node<T> {
    value: T,
    pre: Option<Rc<RefCell<Node<T>>>>,
    next: Option<Rc<RefCell<Node<T>>>>,
}

impl<T> Node<T> {
    fn new(value: T) -> Rc<RefCell<Node<T>>> {
        Rc::new(RefCell::new(Node {
            value,
            pre: None,
            next: None,
        }))
    }
}

#[derive(Debug)]
struct DoubleLinkedList<T> {
    head: Option<Rc<RefCell<Node<T>>>>,
    tail: Option<Rc<RefCell<Node<T>>>>,
    len: usize,
}

impl<T> DoubleLinkedList<T> {
    fn new() -> DoubleLinkedList<T> {
        DoubleLinkedList {
            head: None,
            tail: None,
            len: 0,
        }
    }

    fn push_front(&mut self, value: T) {
        let new_node = Node::new(value);
        match self.head.take() {
            Some(old) => {
                new_node.borrow_mut().next = Some(old.clone());
                old.borrow_mut().pre = Some(new_node.clone());
                self.head = Some(new_node);
                self.len += 1;
            }
            None => {
                self.tail = Some(new_node.clone());
                self.head = Some(new_node.clone());
                self.len += 1;
            }
        }
    }

    fn push_back(&mut self, value: T) {
        let new_node = Node::new(value);
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_node.clone());
                new_node.borrow_mut().pre = Some(old_tail);
                self.tail = Some(new_node);
            }
            None => {
                self.head = Some(new_node.clone());
                self.tail = Some(new_node);
            }
        }
    }

    // 从链表头部移除节点
    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            match old_head.borrow_mut().next.take() {
                Some(new_head) => {
                    new_head.borrow_mut().pre.take();
                    self.head = Some(new_head);
                }
                None => {
                    self.tail.take();
                }
            }
            Rc::try_unwrap(old_head).ok().unwrap().into_inner().value
        })
    }

    // 从链表尾部移除节点
    fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            match old_tail.borrow_mut().pre.take() {
                Some(new_tail) => {
                    new_tail.borrow_mut().next.take();
                    self.tail = Some(new_tail);
                }
                None => {
                    self.head.take();
                }
            }
            Rc::try_unwrap(old_tail).ok().unwrap().into_inner().value
        })
    }

    fn print(&self)
    where
        T: std::fmt::Debug,
    {
        let mut current = self.head.clone();
        while let Some(node) = current {
            print!("{:?} <-> ", node.borrow().value);
            current = node.borrow().next.clone();
        }
        println!("None");
    }
}

struct MiniVec<T> {
    data: *mut (usize, usize, T),
}

impl<T> MiniVec<T> {
    fn new() -> MiniVec<T> {
        let data = unsafe { std::alloc::alloc(std::alloc::Layout::new::<(usize, usize, T)>()) };
        MiniVec {
            data: data as *mut (usize, usize, T),
        }
    }
}

#[test]
fn test_double_linked_list() {
    let mut list = DoubleLinkedList::new();
    list.push_front(1);
    list.push_front(2);
    list.push_front(3);
    list.push_back(4);
    list.print();
}
